﻿#include <iostream>
#include <assert.h>
#include <queue>
#include "Graph.h"

//             D
//           / |  \
//         9   7   16
//       /     |    \
//      A--15--C--14-E
//       \     |     /
//        3    2  200
//         \   | /
//             B

#define EXISTS_IN_MAP(TARGET, MAP) (MAP.find(TARGET) != MAP.end())

#define CLEAR_HEAP(HEAP) size_t size = HEAP.size(); for (int i = 0; i < size; i++) { HEAP.pop(); }

static struct WeightComparator
{
	bool operator()(const GraphEdge* edge1, const GraphEdge* edge2)
	{
		return edge1->weight > edge2->weight;
	}
};

static void dijketra(Graph* graph, GraphNode* startNode, unordered_map<GraphNode*, int>& paths)
{
	priority_queue<GraphEdge*, vector<GraphEdge*>, WeightComparator> sortedHeap;
	unordered_set<GraphNode*> appearNodes;
	paths.insert({ startNode, 0 });
	appearNodes.insert(startNode);
	
	auto cur = startNode;
	
	while (appearNodes.size() < graph->nodes.size())
	{
		for (auto edgeIterator = cur->edges.begin(); edgeIterator != cur->edges.end(); ++edgeIterator)
		{
			auto edge = *edgeIterator;
			if (!EXISTS_IN_MAP(edge->to, appearNodes))
			{
				sortedHeap.push(*edgeIterator);
				auto originalFromPair = paths.find(edge->from);
				int originalWeight = 0;
				if (originalFromPair != paths.end())
				{
					originalWeight = originalFromPair->second;
				}

				auto originalToPair = paths.find(edge->to);
				if (originalToPair == paths.end() || originalWeight + edge->weight < originalToPair->second)
				{
					paths[edge->to] = originalWeight + edge->weight;
				}
			}
		}

		if (sortedHeap.size() > 0)
		{
			auto topEdge = sortedHeap.top();
			sortedHeap.pop();

			cur = topEdge->to;
			appearNodes.insert(cur);
		}
		else
		{
			//assert(0, "found loop\n");

			// 查找下一个点的过程陷入了一个环，需要跳出这个环
			for (auto edgeIterator = graph->edges.begin(); edgeIterator != graph->edges.end(); edgeIterator++)
			{
				auto edge = *edgeIterator;
				if (!EXISTS_IN_MAP(edge->from, appearNodes))
				{
					cur = edge->to;
					appearNodes.insert(cur);
					break;
				}

				if (!EXISTS_IN_MAP(edge->to, appearNodes))
				{
					cur = edge->from;
					appearNodes.insert(cur);
					break;
				}
			}
		}

		CLEAR_HEAP(sortedHeap);
	}
}

/**
 * Dijkstra算法, 单元最短路径算法，即从一个指定的节点到另外任意节点的最短路径
 * 适用范围: 没有权值累加和为负数的环
 *
 *              D
 *            / |  \
 *          9   7   16
 *        /     |    \
 *       A--15--C--14-E
 *        \     |     /
 *         3    2  200
 *          \   | /
 *              B
 *
 * 
 *  上图，从A点出发，到达各个点的最短路径：
 *    | B  C  D  E
 *  A | 3  5  9 19
 *
 *  先假设：
 *    | A  B  C  D  E
 *  A | 0  ∞  ∞  ∞  ∞
 *
 *  之后，从A出发有三条路线，A-3-B, A-15-C, A-9-D, 依次更新表格
 *    | A  B  C  D  E
 *  A | 0  3 15  9  ∞
 *
 *  选择最短路径A-3-B，来到B点，从B出发有三条路线，B-3-A，B-2-C, B-200-E,
 *  对于B-3-A, A-B-A长度是6，> 0, 跳过；对于B-2-C，可知A-B-C的路径比原来A-C短，可以更新；A-B-E的长度是3+200=203，比∞小，可以更新。然后依次更新表格
 *    | A  B  C  D  E
 *  A | 0  3  5  9 203
 *
 *  然后选择最短路径B-C，来到C点，从C出发有四条路线，C-15-A, C-2-B, C-7-D, C-14-E,
 *  对于C-15-A, A-C-A长度是20，大于0，跳过；对于C-2-B，A-C-B长度是7，大于3，跳过；对于C-7-D, 可知A-C-D的路径长度为5+7=12，大于9，不更新；
 *  对于C-14-E，可知A-B-C-E的路径长度是5+14=19，比原来小，可以更新。然后依次更新表格
 *    | A  B  C  D  E
 *  A | 0  3  5  9 19
 *
 *  然后选择最短路径C-D，来到D点，从D点出发有三条路线，D-9-A, D-7-C, D-16-E,
 *  对于D-9-A, A-D-A长度是18，大于0，跳过；对于D-7-C, A-D-C长度是16，大于5，跳过；对于D-16-E, A-D-E长度是25，大于19，跳过。不更新表格。
 *
 *  故最终表格是:
 *
 *    | A  B  C  D  E
 *  A | 0  3  5  9 19
 *
 *  上述的方式也可以理解为，每处理下一个点的时候，即可将上一个点锁定，也就是以后再也不去改了，比如，处理完B点该处理C点的时候，A-B的最短距离就锁定了，
 *  以后也不会再修改A-B的距离了；处理完C点该处理D点的时候，A-C的最短距离也就锁定了。
 *
 */
int main_Dijkstra()
{
	int matrix[][3] = {
		{'a', 'b', 3},
		{'a', 'c', 15},
		{'a', 'd', 9},
		{'b', 'c', 2},
		{'b', 'e', 200},
		{'c', 'd', 7},
		{'c', 'e', 14},
		{'d', 'e', 16},
	};

	//int matrix[][3] = {
	//	{'a', 'b', 6},
	//	{'a', 'c', 1},
	//	{'a', 'd', 5},
	//	{'b', 'c', 5},
	//	{'b', 'e', 3},
	//	{'c', 'd', 5},
	//	{'c', 'e', 6},
	//	{'c', 'f', 4},
	//	{'d', 'f', 2},
	//	{'e', 'f', 6},
	//};

	int* pMatrix = matrix[0];
	auto graph = Graph::generate(&pMatrix, sizeof(matrix) / sizeof(int) / 3, 3, false);

	unordered_map<GraphNode*, int> paths;
	dijketra(graph, graph->nodes.at('a'), paths);

	for (auto pairIterator = paths.begin(); pairIterator != paths.end(); pairIterator++)
	{
		printf("%c %d\n", pairIterator->first->value, pairIterator->second);
	}

	delete(graph);

	return 0;
}